//
//  39. 组合总和.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/8/29.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution39 {
    // 组合总和
    // ”candidates里无重复元素“ 这个条件很关键。如果有重复元素，还得去重。
    // 如果只是求最少或者最多有多少组合数，可以是完全背包问题
    // 如果是每一种怎么组合的，就需要用回溯，求出具体的组合
    // 此题是可以重复的组合
    var result: [[Int]] = []
    var path: [Int] = []
    var sum: Int = 0
    func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        backTrace(candidates, target, start: 0)
        return result
    }
    func backTrace(_ candidates: [Int],_ target: Int, start: Int) {
        if sum == target {
            result.append(path)
            return
        }
        // sum + candidates[i] <= target 才进入递归（提前剪枝了）
        // 提前剪枝的时间能在leetcode上能明显感觉出来
        for i in start..<candidates.count where sum + candidates[i] <= target {
            sum += candidates[i]
            path.append(candidates[i])
            // 无重复集合
            // start从i开始很关键，可以在一个集合里使用相同的多次。
            // candidate里无重复的元素也很关键，这样从i开始在树枝上就一定不会出现集合重复的情况。
            backTrace(candidates, target, start: i)
            path.removeLast()
            sum -= candidates[i]
        }
    }
   
    static func test() {
        let solution = Solution39()
        let candidates = [2,3,5]
        let target = 8
        let result = solution.combinationSum(candidates, target)
        print(result)
    }
}
